class BinarySearchTree():
    "Implements a Python varient of a Binary Search Tree"
    def __init__(self):
        self.root = None

    def __len__(self):
        "Overrides len() function to count al of the nodes in the BST"
        return self.length(self.root)

    def length(self, node):
        "Recursive helper method to count nodes"
        if node == None:
            return 0
        else:
            return self.length(node.getLeft()) + self.length(node.getRight()) + 1
        
    def add(self, datatype):
        "Adds a TreeNode to its correct place in the tree, with smaller items to the right and greater ones to the left"
        self.root = self.__add__(self.root, datatype)
        
    def __add__(self, node, dat):
        if node == None:
            return TreeNode(dat)
        else:
            if dat < node.getData():
                node.left = self.__add__(node.left, dat)
            elif dat > node.getData():
                node.right = self.__add__(node.right, dat)
        return node

    def inorder(self):
        "returns a list of each node's data in ascending order"
        self.items = []
        self.__inorder__(self.root)
        return self.items
        
    def __inorder__(self, n):
        if(n == None):
            return ''
        else:
            self.__inorder__(n.getLeft())
            self.items.append(n.getData())
            self.__inorder__(n.getRight())

    def preorder(self):
        "returns a list of each node's data in preorder"
        self.items = []
        self.__preorder__(self.root)
        return self.items
        
    def __preorder__(self, n):
        if(n == None):
            return ''
        else:
            self.items.append(n.getData())
            self.__preorder__(n.getLeft())
            self.__preorder__(n.getRight())

    def postorder(self):
        "returns a list of each node's data in postorder"
        self.items = []
        self.__postorder__(self.root)
        return self.items
        
    def __postorder__(self, n):
        if(n == None):
            return ''
        else:
            self.__postorder__(n.getLeft())
            self.__postorder__(n.getRight())
            self.items.append(n.getData())
                
class TreeNode():
    """Node that contains  pointers to left and right nodes"""
    data = ""
    left = None
    right = None

    def __init__(self, string = ''):
        self.data = string
        self.left = None
        self.right = None
        
    def __str__(self):
        return (self.data)
        
    def getLeft(self):
        if self.left != None:
            return self.left

    def getRight(self):
        if self.right != None:
            return self.right

    def getData(self):
        return self.data

